package vip.meeet.algorithm.link;

import java.util.HashMap;
import java.util.Map;


public class Num25 {

    public static void main(String[] args) {

//        ListNode listNode = build("12345");
        ListNode listNode = build("1234567");
        print(listNode);
        ListNode rs = reverseKGroup(listNode, 2);
        print(rs);
    }

    public static ListNode reverseKGroup(ListNode head, int k) {
        int count = 0;
        ListNode tmp = head;
        HashMap<Integer, ListNode> map = new HashMap<>();
        do{
            map.put(count++,tmp);
            tmp = tmp.next;
        }while (tmp != null);

        int turn = count / k;
        if(turn == 0){
            return head;
        }
        for(int i=0;i<turn;i++){
            int start = k * i;
            int end = start + k / 2;
            int run = 0;
            for(int j=start;j<end;j++){
                int metric = start + k - run - 1;
                if(j == 0){
                    head = map.get(metric);
                }
//                swap(map.get(j),map.get(metric));
                swap(map,j,metric);
                run++;
            }
        }
        return head;
    }

    public static void swap(Map<Integer,ListNode> map, int indexA, int indexB){
        ListNode nodeA = map.get(indexA);
        ListNode nodeB = map.get(indexB);
        ListNode tmp;
        if(nodeA.next == nodeB){
            nodeA.next = nodeB.next;
            nodeB.next = nodeA;
        }else {
            tmp = nodeA.next;
            nodeA.next = nodeB.next;
            nodeB.next = tmp;
        }
        tmp = nodeA;
        nodeA = nodeB;
        nodeB = tmp;

        ListNode pre = map.get(indexA - 1);
        if(pre != null){
            pre.next = nodeB;
        }

        pre = map.get(indexB - 1);
        if(pre != null){
            pre.next = nodeA;
        }

    }

    public static void swap(ListNode nodeA,ListNode nodeB){
        ListNode tmp;
        if(nodeA.next == nodeB){
            nodeA.next = nodeB.next;
            nodeB.next = nodeA;
        }else {
            tmp = nodeA.next;
            nodeA.next = nodeB.next;
            nodeB.next = tmp;
        }
        tmp = nodeA;
        nodeA = nodeB;
        nodeB = tmp;
    }

    public static ListNode build(String num){
        ListNode first = new ListNode(Integer.parseInt(String.valueOf(num.charAt(0))));
        ListNode tmp = first;
        for(int i=1;i<num.length();i++){
            ListNode cur = new ListNode(Integer.parseInt(String.valueOf(num.charAt(i))));
            tmp.next = cur;
            tmp = cur;
        }
        return first;
    }

    public static void print(ListNode node){
        StringBuilder sb = new StringBuilder();
        do{
            sb.append(node.val).append(" -> ");
            node = node.next;
        }while (node != null);
        System.out.println(sb.subSequence(0,sb.length() - 4));
    }

    public static class ListNode {
      int val;
      ListNode next;
      ListNode(int x) { val = x; }
   }

}
